import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

public class Demo {
    public ListNode removeElements(ListNode head, int val) {
        if(head == null) {
            return null;
        }
        ListNode cur = head.next;
        ListNode prev = head;
        while(cur != null) {
            if(cur.val == val) {
                prev.next = cur.next;
                cur = prev.next;
            }else {
                prev = prev.next;
                cur = cur.next;
            }
        }
        if(head.val == val) {
            head = head.next;
        }
        return head;
    }
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;
        int lenA = 0;
        int lenB = 0;
        while(curA != null) {
            curA = curA.next;
            lenA++;
        }
        while(curB != null) {
            curB = curB.next;
            lenB++;
        }
        // 已经统计出了 链表 A B 的长度了
        int len = Math.abs(lenA - lenB);
        if(lenA > lenB) {
            while(len > 0) {
                headA = headA.next;
                len--;
            }
        }else {
            while(len > 0) {
                headB = headB.next;
                len--;
            }
        }
        // 现在成功让 链表A B在同一起点了
        while(headA != null) {
            if(headA == headB) {
                return headA;
            }else {
                headA = headA.next;
                headB = headB.next;
            }
        }
        return null;
    }
    public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while(slow != fast) {
            if(fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }
    public ListNode detectCycle(ListNode head) {
        if(head == null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null) {
            slow = slow.next;
            if(fast.next != null) {
                fast = fast.next.next;
            }else {
                return null;
            }
            if(fast == slow) {
                ListNode node = head;
                while(node != slow) {
                    node = node.next;
                    slow = slow.next;
                }
                return node;
            }
        }
        return null;
    }
    public ListNode detectCycle2(ListNode head) {
        if(head == null) {
            return null;
        }
        ListNode cur = head;
        Set<ListNode> set = new HashSet<>();
        while(cur != null) {
            if(!set.contains(cur)) {
                set.add(cur);
            }else {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }
}
